/*
 * INSANE - Interactive Structural Analysis Environment
 *
 * Copyright (C) 2003-2005
 * Universidade Federal de Minas Gerais
 * Escola de Engenharia
 * Departamento de Engenharia de Estruturas
 * 
 * Author's email :    insane@dees.ufmg.br
 * Author's website :  http://www.dees.ufmg.br/insane
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */

package br.ufmg.dees.insane.model.geo.computationalGeometry.triangulation;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Vector;

/**
 * 
 * @author Penna,S.S. & Pitangueira, Roque
 * @since 19/10/2006
 * 
 * Delaunay.java
 *
 * Adapted from: 
 * 2D Delaunay Triangulation Java Applet 
 * Author: Luke Sunder Parige
 * E-Mail: parige@ews.uiuc.edu
 * Date  : August 10, 1999
 *              
 */
public class Delaunay extends Triangulation{

    private Vector<NodeD> nodes;
    private Vector<EdgeD> edges;
    private Vector<TriangleD> tris; 
    private EdgeD hullStart;
    private EdgeD actE;

    public Delaunay(LinkedList vertices){
    	super(vertices);
    	super.del = this;
        tris=new Vector<TriangleD>();
        nodes=new Vector<NodeD>();
        edges=new Vector<EdgeD>();
    }

    public Delaunay(int size){
        tris=new Vector<TriangleD>();
        nodes=new Vector<NodeD>();
        edges=new Vector<EdgeD>();
    }
    
    public void Clear(){
        nodes.removeAllElements();
        edges.removeAllElements();
        tris.removeAllElements();
    }
    
    public void Insert(double px, double py){
        int eid;
        NodeD nd=new NodeD(px,py);
        nodes.addElement(nd);
        
        if(nodes.size()<3){
            return;
        }
        
        if(nodes.size()==3){    // create the first triangle
            NodeD p1=(NodeD)nodes.elementAt(0);
            NodeD p2=(NodeD)nodes.elementAt(1);
            NodeD p3=(NodeD)nodes.elementAt(2);
            EdgeD e1=new EdgeD(p1,p2);
            if(e1.onSide(p3)==0){
                nodes.removeElement(nd); 
             return; 
            }
            if(e1.onSide(p3)==-1){  // right side
                p1=(NodeD)nodes.elementAt(1);
                p2=(NodeD)nodes.elementAt(0);
                e1.update(p1,p2);
            }
            EdgeD e2=new EdgeD(p2,p3);
            EdgeD e3=new EdgeD(p3,p1);
            e1.setNextH(e2);
            e2.setNextH(e3);
            e3.setNextH(e1);
            hullStart=e1;
            tris.addElement(new TriangleD(edges,e1,e2,e3));
            return;
        }
        actE=(EdgeD)edges.elementAt(0);
        if(actE.onSide(nd)==-1){ 
            if(actE.getInvE()==null){
                eid=-1;
            }else{
                eid=SearchEdge(actE.getInvE(),nd);
            }
        }else{
            eid=SearchEdge(actE,nd);
        }
        if(eid==0){
            nodes.removeElement(nd);
            return;
        }
        if(eid>0){ 
            ExpandTri(actE,nd,eid);   // nd is inside or on a triangle
        }else{
            ExpandHull(nd);                // nd is outside convex hull
        }
         
    }
    
    public void Insert(NodeD node){
        int eid;
        NodeD nd=node;
        nodes.addElement(nd);
        
        if(nodes.size()<3){
            return;
        }
        
        if(nodes.size()==3){    // create the first triangle
            NodeD p1=(NodeD)nodes.elementAt(0);
            NodeD p2=(NodeD)nodes.elementAt(1);
            NodeD p3=(NodeD)nodes.elementAt(2);
            EdgeD e1=new EdgeD(p1,p2);
            if(e1.onSide(p3)==0){
                nodes.removeElement(nd); 
             return; 
            }
            if(e1.onSide(p3)==-1){  // right side
                p1=(NodeD)nodes.elementAt(1);
                p2=(NodeD)nodes.elementAt(0);
                e1.update(p1,p2);
            }
            EdgeD e2=new EdgeD(p2,p3);
            EdgeD e3=new EdgeD(p3,p1);
            e1.setNextH(e2);
            e2.setNextH(e3);
            e3.setNextH(e1);
            hullStart=e1;
            tris.addElement(new TriangleD(edges,e1,e2,e3));
            return;
        }
        actE=(EdgeD)edges.elementAt(0);
        if(actE.onSide(nd)==-1){ 
            if(actE.getInvE()==null){
                eid=-1;
            }else{
                eid=SearchEdge(actE.getInvE(),nd);
            }
        }else{
            eid=SearchEdge(actE,nd);
        }
        if(eid==0){
            nodes.removeElement(nd);
            return;
        }
        if(eid>0){ 
            ExpandTri(actE,nd,eid);   // nd is inside or on a triangle
        }else{
            ExpandHull(nd);                // nd is outside convex hull
        }
         
    }
     
    public void Delete(double px, double py){
         
        if(nodes.size()<=3){
            return;   // not allow deletion for only 1 triangle
        }
        NodeD nd=Nearest((double)px,(double)py);
        if(nd==null){
            return;          // not found
        }
        nodes.removeElement(nd);
        EdgeD e,ee,start;
        start=e=nd.GetEdge().MostRight();
        int nodetype=0;
        int idegree=-1;
        EdgeD index[]=new EdgeD[100];
        while(nodetype==0){
            edges.removeElement(ee=e.getNextE());
            index[++idegree]=ee;
            ee.AsIndex();
            tris.removeElement(e.getTri());   
            edges.removeElement(e);
            edges.removeElement(ee.getNextE());
            e=ee.getNextE().getInvE();           
            if(e==null){
                nodetype=2;        
            }
            if(e==start){
                nodetype=1;
            }
         } 
          
         // Generate new triangles and add to triangulation
         int cur_i=0,cur_n=0;
         int last_n=idegree;
         EdgeD e1=null,e2=null,e3;
         while(last_n>=1){
             e1=index[cur_i];
             e2=index[cur_i+1];
             if(last_n==2 && nodetype==1){
                 tris.addElement(new TriangleD(edges,e1,e2,index[2]));
                 SwapTest(e1);
                 SwapTest(e2);
                 SwapTest(index[2]);
                 break;
             }
             if(last_n==1 && nodetype==1){
                 index[0].getInvE().LinkSymm(index[1].getInvE());
                 index[0].getInvE().AsIndex();
                 index[1].getInvE().AsIndex();
                 SwapTest(index[0].getInvE());
                 break;
             }
             if(e1.onSide(e2.getP2())==1){  // left side
                 e3=new EdgeD(e2.getP2(),e1.getP1());
                 cur_i+=2;
                 index[cur_n++]=e3.MakeSymm();
                 tris.addElement(new TriangleD(edges,e1,e2,e3));
                 SwapTest(e1);
                 SwapTest(e2);
             }else{
                 index[cur_n++]=index[cur_i++];
             }
             if(cur_i==last_n){
                 index[cur_n++]=index[cur_i++];
             }
             if(cur_i==last_n+1){
                 if(last_n==cur_n-1){
                     break;
                 }
                 last_n=cur_n-1;
                 cur_i=cur_n=0;
             }
         }
         
         if(nodetype==2){   // reconstruct the convex hull
             index[last_n].getInvE().MostLeft().setNextH(hullStart=index[last_n].getInvE());
             for(int i=last_n;i>0;i--){
                 index[i].getInvE().setNextH(index[i-1].getInvE());
                 index[i].getInvE().setInvE(null);
             }
             index[0].getInvE().setNextH(start.getNextH());
             index[0].getInvE().setInvE(null);
         }
    }
      
    private void ExpandTri(EdgeD e, NodeD nd, int type){
        EdgeD e1=e;
        EdgeD e2=e1.getNextE();
        EdgeD e3=e2.getNextE();
        NodeD p1=e1.getP1();
        NodeD p2=e2.getP1();
        NodeD p3=e3.getP1();
        if(type==2){    // nd is inside of the triangle
            EdgeD e10=new EdgeD(p1,nd);
            EdgeD e20=new EdgeD(p2,nd);
            EdgeD e30=new EdgeD(p3,nd);
            e.getTri().RemoveEdges(edges);
            tris.removeElement(e.getTri());     // remove old triangle
            tris.addElement(new TriangleD(edges,e1,e20,e10.MakeSymm()));
            tris.addElement(new TriangleD(edges,e2,e30,e20.MakeSymm()));
            tris.addElement(new TriangleD(edges,e3,e10,e30.MakeSymm()));
            SwapTest(e1);   // swap test for the three new triangles
            SwapTest(e2);
            SwapTest(e3);
        }else{           // nd is on the edge e
            EdgeD e4=e1.getInvE();
            if(e4==null || e4.getTri()==null){  // one triangle involved
                EdgeD e30=new EdgeD(p3,nd);
                EdgeD e02=new EdgeD(nd,p2);
                EdgeD e10=new EdgeD(p1,nd);
                EdgeD e03=e30.MakeSymm();
                e10.AsIndex();
                e1.MostLeft().setNextH(e10);
                e10.setNextH(e02);
                e02.setNextH(e1.getNextH());
                hullStart=e02;
                tris.removeElement(e1.getTri()); // remove oldtriangle               // add two new triangles
                edges.removeElement(e1);
                edges.addElement(e10);
                edges.addElement(e02);
                edges.addElement(e30);
                edges.addElement(e03);
                tris.addElement(new TriangleD(e2,e30,e02));
                tris.addElement(new TriangleD(e3,e10,e03));
                SwapTest(e2);   // swap test for the two new triangles
                SwapTest(e3);
                SwapTest(e30);
              }else{       // two triangle involved
                  EdgeD e5=e4.getNextE();
                  EdgeD e6=e5.getNextE();
                  NodeD p4=e6.getP1();
                  EdgeD e10=new EdgeD(p1,nd);
                  EdgeD e20=new EdgeD(p2,nd);
                  EdgeD e30=new EdgeD(p3,nd);
                  EdgeD e40=new EdgeD(p4,nd);
                  tris.removeElement(e.getTri());  // remove oldtriangle
                  e.getTri().RemoveEdges(edges);
                  tris.removeElement(e4.getTri()); // remove old triangle
                  e4.getTri().RemoveEdges(edges);
                  e5.AsIndex();   // because e, e4 removed, reset edge index of node p1 and p2
                  e2.AsIndex();
                  tris.addElement(new TriangleD(edges,e2,e30,e20.MakeSymm()));
                  tris.addElement(new TriangleD(edges,e3,e10,e30.MakeSymm()));
                  tris.addElement(new TriangleD(edges,e5,e40,e10.MakeSymm()));
                  tris.addElement(new TriangleD(edges,e6,e20,e40.MakeSymm()));
                  SwapTest(e2);   // swap test for the three new triangles
                  SwapTest(e3);
                  SwapTest(e5);
                  SwapTest(e6);
                  SwapTest(e10);
                  SwapTest(e20);
                  SwapTest(e30);
                  SwapTest(e40);
              }
        }
      }
    
    private void ExpandHull(NodeD nd){
         EdgeD e1,e2,e3=null,enext;
         EdgeD e=hullStart;
         EdgeD comedge=null,lastbe=null;
         
         while(true){
             enext=e.getNextH();
             if(e.onSide(nd)==-1){   // right side
                 if(lastbe!=null){
                     e1=e.MakeSymm();
                     e2=new EdgeD(e.getP1(),nd);
                     e3=new EdgeD(nd,e.getP2());
                     if(comedge==null){
                         hullStart=lastbe;
                         lastbe.setNextH(e2);
                         lastbe=e2;
                     }else{
                         comedge.LinkSymm(e2);
                     }
                     comedge=e3;
                     //tris.addElement(new Triangle(edges,e3,e2,e1));
                     tris.addElement(new TriangleD(edges,e1,e2,e3));
                     SwapTest(e);
                 }
             }else{
                 if(comedge!=null){
                     break;
                 }
                 lastbe=e;
             }
             e=enext;
         }
    
         lastbe.setNextH(e3);
         e3.setNextH(e);
    }
    
    private int SearchEdge(EdgeD e, NodeD nd){
       int f2,f3;
       EdgeD e0=null;
       if((f2=e.getNextE().onSide(nd))==-1){
           if(e.getNextE().getInvE()!=null){
               return SearchEdge(e.getNextE().getInvE(),nd);
           }else{
               actE=e; return -1;
           }
       }
       if(f2==0){
           e0=e.getNextE();
       }
       EdgeD ee=e.getNextE();
       if((f3=ee.getNextE().onSide(nd))==-1){ 
           if(ee.getNextE().getInvE()!=null){
               return SearchEdge(ee.getNextE().getInvE(),nd);
           }else{ 
               actE=ee.getNextE(); return -1;
           }
       }
       if(f3==0){
           e0=ee.getNextE();
       }
       if(e.onSide(nd)==0){
           e0=e;
       }
       if(e0!=null){
           actE=e0;
           if(e0.getNextE().onSide(nd)==0) {actE=e0.getNextE(); return 0;}
           if(e0.getNextE().getNextE().onSide(nd)==0) return 0;
           return 1;
       }
       actE=ee;
       return 2;
    }
    
    private void SwapTest(EdgeD e11){
        EdgeD e21=e11.getInvE();
        if(e21==null || e21.getTri()==null) return;
        EdgeD e12=e11.getNextE();
        EdgeD e13=e12.getNextE();
        EdgeD e22=e21.getNextE();
        EdgeD e23=e22.getNextE();
        if(e11.getTri().inCircle(e22.getP2()) || e21.getTri().inCircle(e12.getP2())){
            e11.update(e22.getP2(),e12.getP2());
            e21.update(e12.getP2(),e22.getP2());
            e11.LinkSymm(e21);
            e13.getTri().update(e13,e22,e11);
            e23.getTri().update(e23,e12,e21);
            e12.AsIndex();
            e22.AsIndex();
            SwapTest(e12);
            SwapTest(e22);
            SwapTest(e13);
            SwapTest(e23);
        }
    }
      
    private NodeD Nearest(double x, double y){
        // locate a node nearest to (px,py)
        double dismin=0.0,s;
        NodeD nd=null;
        for(int i=0;i<nodes.size();i++)
          {
            s=((NodeD)nodes.elementAt(i)).Distance(x,y);
            if(s<dismin||nd==null) { dismin=s;nd=(NodeD)nodes.elementAt(i);}
          }
        return nd;
    }
    
    public Vector getTris() {
        return tris;
    }
    
    public void setTris(Vector<TriangleD> tris) {
        this.tris = tris;
    }
    
    public static void main(String[] args){
        Delaunay dt = new Delaunay(0);
        dt.Insert(0.0,0.0);
        dt.Insert(1.0,0.0);
        dt.Insert(1.0,1.0);
        dt.Insert(0.0,1.0);
        dt.Insert(0.5,0.5);
        for (int i=0; i<dt.tris.size(); i++)
        { TriangleD t=(TriangleD)dt.tris.elementAt(i);
          System.out.println("*********** "+  dt.tris.size()  +" *******************");
          System.out.println(t.anEdge.p1.x+" "+t.anEdge.p1.y);
          System.out.println( t.anEdge.getNextE().p1.x+" "+ t.anEdge.getNextE().p1.y);
          System.out.println(t.anEdge.getNextE().getNextE().p1.x+" "+t.anEdge.getNextE().getNextE().p1.y);
        
        }
    }
    
//****************************************************************************************************************   
}//end of this class

/**
 * @author Penna,S.S. & Pitangueira, Roque
 * @since 19/10/2006
 * 
 * Adapted from: 
 * 2D Delaunay Triangulation Java Applet 
 * Author: Luke Sunder Parige
 * E-Mail: parige@ews.uiuc.edu
 * Date  : August 10, 1999
 */
class NodeD {
     double   x,y;
     EdgeD anEdge;
     char  type;
     String label = "";
	 HashMap<String, Object> values;
	 
     
     public NodeD(double x, double y){
         this.x=x; this.y=y;anEdge=null;
     }
     
     public NodeD(double x, double y, String aLabel){
         this.x=x; 
         this.y=y;
         anEdge=null;
         this.label = aLabel;
     }
     
     public EdgeD GetEdge(){
         return anEdge;
     }

     public double Distance(double px, double py){ 
         double dx=px-x;
         double dy=py-y;
         return (Math.sqrt(dx*dx+dy*dy));
     }
//********************************************************************************************
}//end of this class

/**
 * @author Penna,S.S. & Pitangueira, Roque
 * @since 19/10/2006
 * 
 * Adapted from: 
 * 2D Delaunay Triangulation Java Applet 
 * Author: Luke Sunder Parige
 * E-Mail: parige@ews.uiuc.edu
 * Date  : August 10, 1999
 */
class EdgeD extends Object{
     
    // start and end point of the edge
    public NodeD p1,p2; 
    // inverse edge (p2->p1)
    public EdgeD invE=null;
    // next edge in the triangle in countclickwise     
    public EdgeD nextE=null; 
     // convex hull link   
    public EdgeD nextH=null; 
    // triangle containing this edge   
    public TriangleD inT=null;  
    // line equation parameters. aX+bY+c=0   
    public double a,b,c;

    // Constructor
    public EdgeD(NodeD p1, NodeD p2) { 
       update(p1,p2);
    }
    
    // update method
    public void update(NodeD p1, NodeD p2) {
        this.p1=p1; 
        this.p2=p2; 
        Setabc(); 
        AsIndex(); 
    }
    
    public NodeD getP1(){
        return p1;
    }
    
    public NodeD getP2(){
        return p2;
    }
    
    public EdgeD getInvE(){
        return invE;
    }
    
    public void setInvE(EdgeD e){
        invE=e;
    }
    
    public EdgeD getNextE(){
        return nextE;
    }
    
    public void setNextE(EdgeD e){
        nextE=e;
    }
    
    public EdgeD getNextH(){
        return nextH;
    }
    
    public void setNextH(EdgeD e){
        nextH=e;
    }
   
    public TriangleD getTri(){
        return inT;
    }

    public void setTri(TriangleD t){
        inT=t;
    }
    
    public EdgeD MakeSymm(){
        EdgeD e = new EdgeD(p2,p1); 
        LinkSymm(e); 
        return e; 
    }

    public void LinkSymm(EdgeD e){
        this.invE=e; 
        if(e!=null){
            e.invE=this; 
        }
    }

    public int onSide(NodeD nd){ 
        double s=a*nd.x+b*nd.y+c;
        if(s>0.0){
            return 1;
        }
        if(s<0.0){
            return -1;
        }
        return 0;
    }
    
    // Method for setting parameters of a,b,c
    void Setabc()   
       { a=p2.y-p1.y; b=p1.x-p2.x; c=p2.x*p1.y-p1.x*p2.y; }
    void AsIndex()  { p1.anEdge=this;}
    
    EdgeD MostLeft() { 
         EdgeD ee,e=this;
         while((ee=e.getNextE().getNextE().getInvE())!=null && ee!=this)
             e=ee;
         return e.getNextE().getNextE();
    }
       
    EdgeD MostRight() {
        EdgeD ee,e=this;
      while(e.getInvE()!=null && (ee=e.getInvE().getNextE())!=this){
          e=ee;
      }
      return e;
    }
    
//******************************************************************************************    
}//end of this class

/**
 * @author Penna,S.S. & Pitangueira, Roque
 * @since 19/10/2006
 * 
 * Adapted from: 
 * 2D Delaunay Triangulation Java Applet 
 * Author: Luke Sunder Parige
 * E-Mail: parige@ews.uiuc.edu
 * Date  : August 10, 1999
 */
class TriangleD {
     
    EdgeD    anEdge;
    double  circumCirX;  
    double  circumCirY;
    double  circumCirR; 


    public  TriangleD(EdgeD e1, EdgeD e2, EdgeD e3){
        update(e1,e2,e3);
    }
     
    public  TriangleD(Vector<EdgeD> edges, EdgeD e1, EdgeD e2, EdgeD e3) {
        update(e1,e2,e3);
        edges.addElement(e1);
        edges.addElement(e2);
        edges.addElement(e3);
    }
     
    public void update(EdgeD e1, EdgeD e2, EdgeD e3) {
        anEdge=e1;
        e1.setNextE(e2);
        e2.setNextE(e3);
        e3.setNextE(e1);
        e1.setTri(this);
        e2.setTri(this);
        e3.setTri(this);
        findCircle();
    }
     
    public EdgeD GetEdge(){
        return anEdge;
    }
     
    public boolean inCircle(NodeD nd){
        return nd.Distance(circumCirX,circumCirY)<circumCirR;
    }
     
    public void RemoveEdges(Vector edges)  {
        edges.removeElement(anEdge);
        edges.removeElement(anEdge.getNextE());
        edges.removeElement(anEdge.getNextE().getNextE());
    }
     
    public void findCircle() {
        double x1=(double) anEdge.getP1().x;
        double y1=(double) anEdge.getP1().y;
        double x2=(double) anEdge.getP2().x;
        double y2=(double) anEdge.getP2().y;
        double x3=(double) anEdge.getNextE().getP2().x;
        double y3=(double) anEdge.getNextE().getP2().y;
        double a=(y2-y3)*(x2-x1)-(y2-y1)*(x2-x3);
        double a1=(x1+x2)*(x2-x1)+(y2-y1)*(y1+y2);
        double a2=(x2+x3)*(x2-x3)+(y2-y3)*(y2+y3);
        circumCirX=(a1*(y2-y3)-a2*(y2-y1))/a/2;
        circumCirY=(a2*(x2-x1)-a1*(x2-x3))/a/2;
        circumCirR=anEdge.getP1().Distance(circumCirX,circumCirY);
    }
     
//*****************************************************************************************
}//end of this class